Social Choice

Suppose we are are the hiring committee for econ department. These are 3 candidates and the commitee consists of 3 people.. only one candidate will be selected, so there are three possible outcomes. Each committee member has complete and transitive preferences over candidates.

Key words: completeness and transitive.

• Completeness: for all $x,y\in \mathrm{X}$$x, y \in \mathrm{X}$, we have that $x\succsim y$$x \succsim y$ or $y\succsim x$$y \succsim x$ (or both).

• Transitivity: For all $x,y,z\in X$$x, y, z \in X$, if $x\succsim y$$x \succsim y$ and $y\succsim z$$y \succsim z$, then $x\succsim z$$x \succsim z$.

Given individual preferences, we would like to find the unique preference of the committee, the procedure turning members' preference is called social choice function

Let's define the model now

Model

• Finite set of alternatives $X$$X$

• Finite set of individuals $N$$N$

• Each individual has complete and transivitive preference $\to R_i$$\rightarrow R_i$

The social choice function is

, where $R_i$$R_i$ is the (weak) preference of the society. (This implies indifference may occur)

and we use $P_i$$P_i$ denote the strict preference

$R$$R$ is the soical preference

Examples of social choice functions

1. Ignoring individual preferences:

   $$\begin{array}{}\text{(2)}& f(R_1,\dots ,R_N)=R^{\ast }\text{for any }(R_1,\dots ,R_N)\end{array}$$

2. The majority rule:

   say $x$$x$ and $y$$y$ are two alternatives,

   $$\begin{array}{}\text{(3)}& xRy\leftrightarrow |\{i:x{R}_{i}y\}|\ge |\{i:y{R}_{i}x\}|\end{array}$$

   Let's say 3 committees 1,2,3, their rankings are

   • 1: $A\succsim (R_1)B\succsim (R_1)C$$A \succsim (R_1) B\succsim (R_1) C$​

   • 2: $B\succsim C\succsim A$$B \succsim C\succsim A$​

   • 3: $C\succsim A\succsim B$$C\succsim A \succsim B$

   What is the social choice function?

   • Consider A vs B, 2 committees vote A over B but only one vote B over A, so $ARB$$ARB$.

   • Similarly, we can find $BRC$$BRC$ and $CRA$$CRA$

   • So this social choice function is not transivitive.

3. Dictatorship(独裁)

   $$\begin{array}{}\text{(4)}& f(R_1,\dots ,R_N)=R_i\text{for some }i\end{array}$$

Arrow's Axioms

• Unrestricted domain:

  The social choice function $f$$f$ must consider any possible combination of individual preferences over $X$$X$​​ and gives an outcome.

  $f$$f$ 必须包含 $X$$X$ 上个人偏好关系的所有可能组合。不管个人偏好关系是什么样的，社会福利函数都能产生社会偏好排序。

  Does majority rule satisfies the axiom?

  No, because it does not give us an outcome in the domain.

• Weak Pareto principle (unonimity, 一致同意 everyone agrees)

  if $x{R}_{i}y$$xR_i y$ for $\mathrm{\forall }i$$\forall i$ then $xRy$$xRy$..

  Does These three above examples satisfies this axiom?

  • Dictator: Yes. Because if everyone including the dictator agrees, then it becomes the soical choice

  • Majority: Yes Because if everyone agrees, it becomes majority, then it becomes the soical choice

  • Ignoring? No because everyone agrees does not necessarily imply the social choice agreement.

• Independence of irrelevant alternatives

  Let $R=f(R_1,\dots ,R_N)$$R = f(R_1,\dots, R_N)$ and $\tilde{R}=f({\tilde{R}}_1,\dots ,{\tilde{R}}_N)$$\tilde R = f(\tilde R_1,\dots, \tilde R_N)$ and $x,y\in X$$x,y \in X$​.

  If every individual rank $x$$x$ and $y$$y$ the same way under $R_i$$R_i$ and ${\tilde{R}}_i$$\tilde R_i$, then society rank $x$$x$ and $y$$y$ the same way under $R$$R$ and $\tilde{R}$$\tilde R$​.

  如果在两种不同的规则下每个人都有同样的排序，那么这两种规则下的social choice也一致

   

• No dictatorship

  There is no individual $i$$i$ such that for all $x,y\in X$$x, y \in X$, $x{P}_{i}y\Rightarrow xPy$$xP_i y \Rightarrow xPy$ regardless of the preferences of the other individuals. (没有大独裁者)

Borda Count

Let $X=\{x_1,\dots ,x_n\}$$X = \{x_1,\dots, x_n\}$, There are $n$$n$ alternatives, each individual ranks alternatives from $1$$1$ to $n$$n$​, ranking 1-most preferred, and n-least preferred.

Each alternatives "counts" is the sum of each individuals rank

$x_{k}P{x}_l\leftrightarrow$$x_k P {x_l} \leftrightarrow$ if and only if count on $x_k$$x_k$ $<$$<$ counts on $x_l$$x_l$​

Example

4 people, and 4 alternatives

$X=\{NYC,LA,\text{Miami},\text{Raleigh}\}$$X = \{NYC, LA, \text{Miami}, \text{Raleigh}\}$​

Ranking the best city in USA,

1	2	3	4
NYC	LA	R	M
LA	NYC	NYC	LA
M	M	M	R
R	R	LA	NYC

Here counts:

NYC: 9, LA: 9 Miami:10 Raleigh: 12

then we conclude: $NYC\sim LA\succsim M\succsim R$$NYC \sim LA \succsim M\succsim R$​

But if we changes the third individual's ranking on NYC- R - M - LA

Then counts changes to NYC: 8, LA: 9, Miami: 10, Raleign: 13

Then we conclude becomes $NYC\succsim LA\succsim M\succsim R$$NYC \succsim LA\succsim M\succsim R$

But what we find from this example? It violates the independence of irrelevant assumption

Because the third individual does not change his preference between LA and NYC, but the final ranking changes.

Theorem

Let $|X|\ge 3$$|X| \geq 3$ Then there is no social welfare function $f$$f$ which satisfies all 4 axioms

Homework for Tuesday

1. Show that Borda Count satisfies all other axioms

   Suppose the Borda Count violates Unrestrictive domain axiom, which means we are unable to generate any social preference between $x_k$$x_k$ and $x_l$$x_l$, in other words, we are unable to compare the counts on $x_k$$x_k$ and $x_l$$x_l$. However, we know that counts on $x_k$$x_k$ and $x_l$$x_l$ always satifies one of the following relation:

   $$\begin{array}{}\text{(5)}& \begin{array}{c}\text{count on }{x}_k>\text{count on }{x}_l\\ \text{count on }{x}_k=\text{count on }{x}_l\\ \text{count on }{x}_k<\text{count on }{x}_l\end{array}\end{array}$$

   , which implies that there must be one of the following to be true:

   $$\begin{array}{}\text{(6)}& \begin{array}{c}{x}_{k}P{x}_l\\ x_{k}I{x}_l\\ x_{l}P{x}_k\end{array}\end{array}$$

   This is the proof of completeness.

   Tand suppose $x_{k}P{x}_l$$x_kP x_l$, and $x_{l}P{x}_m$$x_l P x_m$, which implies the count on $x_k>x_l>x_m$$x_k>x_l>x_m$. That proved the transitivity.

   Overall $P$$P$ is well defined over $X$$X$.

 

For Weak Pareto principle. Let's say for each individual $i$$i$, we have $x{R}_{i}y$$xR_iy$, which implies that for all $i\in N$$i\in N$, we have count on $x$$x$ $\le$$\leq$ count on $y$$y$.

Therefore, if we sum all the counts across $i$$i$, then

$$\begin{array}{}\text{(7)}& \sum _i\text{count on }x\le \sum \text{count on }y\end{array}$$

, which implies that $xRy$$xRy$​.

 

For No dictatorship principle. Suppose we have a dictator $l\in N$$l \in N$ whose preference is $x{R}_{l}y$$xR_ly$, i.e. $i$$i$'s counts on $x$$x$ $\le$$\leq$ counts on $y$$y$. Then based on this axiom, no matther what the others' preference are, the social choice function is $xRy$$xRy$. Now, consider an extreme case that all other $i\in N$$i\in N$ and $i\ne l$$i\neq l$, such that $y{R}_{i}x$$y R_i x$ and the sum of counts on $x$$x$ $\ge$$\geq$ counts on $y$$y$. Hence, according to the rule of Borda count, $yRx$$yRx$​, which contradicts to the social preference based on dictator.

Therefore, the Borda count satisfies all other 3 axioms.

 

2. When $|X|=2$$|X| = 2$​​​​​, show Borda count satisfies all 4 axioms

   From the previous question, we have already shown the Borda count satifies axiom of U, WP, and ND.

   So let's consider the IIA when $|X|=2$$|X| = 2$​.

   Let $R=f(R_1,\dots ,R_N)$$R = f(R_1,\dots, R_N)$ and $\tilde{R}=f({\tilde{R}}_1,\dots ,{\tilde{R}}_N)$$\tilde R = f(\tilde R_1,\dots, \tilde R_N)$ and $x,y\in X$$x,y \in X$. And every individual rank $x$$x$ and $y$$y$ the same way under $R_i$$R_i$ and ${\tilde{R}}_i$$\tilde R_i$. Since we only have two alternatives $x$$x$ and $y$$y$, so $R_i={\tilde{R}}_i$$R_i = \tilde R_i$ for all $i$$i$. Then the social choice rank $x$$x$ and $y$$y$ the same way under $R$$R$ and $\tilde{R}$$\tilde R$ as well because $R=\tilde{R}$$R = \tilde R$.

   IIA also satisfies when $|X|=2$$|X | =2$.

 

 

 

Now let's rigorously prove the theorem.

Proof

Step 1:

Let $x\in X$$x\in X$, be the lowest preferred alternative for all $i\in I$$i \in I$.

By Unrestricted domain, Social welfare function chooses a social preference for $(R_i{)}_{i\in R}$$(R_i)_{i\in R}$, i.e. $f(R_1,\dots ,R_m)=R$$f(R_1,\dots,R_m)= R$, (There exists a social choice $R$$R$)

By Weak pareto principle, $x$$x$ is ranked of the bottom under social choice $R$$R$​.

$R_1$$R_1$	$R_2$$R_2$	...	$R_m$$R_m$
$⋮$$\vdots$	$⋮$$\vdots$	$⋮$$\vdots$	$⋮$$\vdots$
$x$$x$	$x$$x$	$x$$x$	$x$$x$

Step 2:

Now, let's do one-by-one, remove $x$$x$ from the bottom of the ranking of each individual to the top, $f$$f$ is well defined under such new ranking profile due to unrestricted domain, and by weak pareto, $x$$x$ is ranked at the top of the new social ranking $R^{\prime }$$R^\prime$​.

$R_1^{\prime }$$R_1^\prime$	$R_2^{\prime }$$R_2^\prime$	...	$R_m^{\prime }$$R_m^\prime$
$x$$x$	$x$$x$
$⋮$$\vdots$	$⋮$$\vdots$	$⋮$$\vdots$	$⋮$$\vdots$
			$x$$x$

So at some point, let's say at individual $n$$n$, after changing the ranking of individual $n$$n$, $x$$x$ becomes the top of the social choice (social ranking).

Claim: There exist $i_n\ne i_m$$i_n\neq i_m$ such that $x$$x$ moves from the bottom to top when we change $i_n$$i_n$ 's ranking.

We can also prove this Claim:

On the controry of some step $x$$x$ move up in the social ranking but not to the top, say one new social choice $\hat{R}$$\hat R$ such that $y\hat{R}x\hat{R}z$$y \hat R x \hat R z$. Then at that step $x$$x$ is either ranked at the bottom or at the top by all individuals.

Then without changing the relative ranking, compared to $x$$x$, we rank $z$$z$ over $y$$y$ for all individuals. say this new social ranking $\tilde{R}$$\tilde R$.

According to WP, $z\tilde{R}y$$z \tilde R y$

According to IIA, $y\hat{R}x$$y \hat R x$ and nobody has changed relative ranking between $y$$y$ and $x$$x$, so under new social ranking, $y\tilde{R}x$$y \tilde R x$, and similarly, $x\hat{R}z\Rightarrow x\tilde{R}z$$x \hat R z \Rightarrow x\tilde R z$. By transversality, $y\tilde{R}z$$y \tilde R z$, contradiction!

Step 3:

Let $y$$y$ and $z$$z$ be any two alternatives, consider the profile in which we change the first $n-1$$n-1$ individuals. Consider $i_n$$i_n$ and change her ranking as $y{R}_n^{\prime }x{R}_n^{\prime }z$$y R_n^\prime x R^\prime _n z$, (under $y{R}_{n}x$$y R_n x$​).

In the new profile $y$$y$ is ranked over $x$$x$ under the social ranking $R^{\prime \prime }$$R^{\prime \prime }$ (IIA), $\Rightarrow y{R}^{\prime \prime }x$$\Rightarrow y R^{\prime \prime }x$, and from t6his intermediate profile and the one all first $n$$n$ individuals ranking $x$$x$ at the top, the relative ranking of $x$$x$ and $z$$z$ the same, Then IIA gives $\Rightarrow x{R}^{\prime \prime }z$$\Rightarrow x R^{\prime \prime } z$. Then by transversality we have $y{R}^{\prime \prime }z$$y R^{\prime \prime }z$.

Notice that independent of the rankings of the other individuals for $y$$y$ and $z$$z$, the social ranking agrees with $i_n$$i_n$'s ranking over $y$$y$ and $z$$z$.

Since $y$$y$ and $z$$z$ are any arbitrary two alternatives, social ranking mimics the ranking of $i_n$$i_n$ for any two alternatives that we choose from $X$$X$. That indicates that $i_n$$i_n$ is a dictator!